
Namespace std
    Public Class trie(Of keyT, valueT, _childCount As _int64, _keyToIndex As _to_uint32(Of keyT))
        Implements ICloneable

        'Public Delegate Function DkeyToIndex(ByRef k As keyT) As UInt32
        Public Delegate Sub DfindFrontAction(ByVal n As node)
        Private Shared _cc As _childCount = Nothing
        Private Shared keyToIndex As _keyToIndex = Nothing
        Private root As node = Nothing

        Public Class iterator
            Inherits randomAccessIterator(Of node)

            Public Sub New()
                MyBase.New()
            End Sub

            Public Sub New(ByVal that As pointer(Of node))
                MyBase.New(that)
            End Sub

            Public Sub New(ByVal that As node)
                MyBase.New(that)
            End Sub

            Protected Function traversalNext() As Boolean
                Dim thisIndex As UInt32
                thisIndex = 0
                While p <> _end
                    Dim i As UInt32
                    For i = thisIndex To p.child.Length() - 1
                        If Not p.child(i) Is Nothing Then
                            p = p.child(i)
                            Exit While
                        End If
                    Next

                    If findFatherIndex(p, thisIndex) Then
                        thisIndex += 1
                        p = p.father
                    Else
                        p = _end.p
                        Exit While
                    End If
                End While

                Return p <> _end
            End Function

            Protected Function traversalPrev() As Boolean
                Dim thisindex As UInt32
                If findFatherIndex(p, thisindex) Then
                    If thisindex > 0 Then
                        Dim i As Int64
                        Dim thisnode As node = Nothing
                        thisnode = p
                        For i = thisindex - 1 To 0 Step -1
                            p = thisnode.father.child(i)
                            If max(p) Then
                                Exit For
                            End If
                        Next
                        If i < 0 Then
                            p = thisnode.father
                        End If
                    Else
                        p = p.father
                    End If
                Else
                    p = _end.p
                End If

                Return p <> _end
            End Function

            Protected Overrides Function traversal(ByVal prev As Boolean) As Boolean
                If prev Then
                    Return traversalPrev()
                Else
                    Return traversalNext()
                End If
            End Function
        End Class

        Public Class node
            Implements ICloneable

            Protected Friend _length As UInt32
            Public hasValue As Boolean
            Public value As valueT

            Protected Friend father As node
            Protected Friend child() As node

            Public Function length() As UInt32
                Return _length
            End Function

            Private Sub initial(ByVal indexCount As UInt32)
                hasValue = False
                ReDim child(indexCount - 1)
                value = alloc(Of valueT)()
                father = Nothing
            End Sub

            Public Sub New(ByVal indexCount As UInt32)
                initial(indexCount)
            End Sub

            Public Sub New()
            End Sub

            Public Function first() As keyT()
                Dim rtn(length() - 1) As keyT
                Dim w As node = Nothing
                w = Me
                For i As Int64 = length() - 1 To 0 Step -1
                    rtn(i) = keyToIndex.reverse(w.fatherIndex())
                    w = w.father
                Next
                assert(w.isRoot())
                Return rtn
            End Function

            Public Function isRoot() As Boolean
                Return father Is Nothing
            End Function

            Public Function fatherIndex() As Int64
                Dim rtn As Int64
                If findFatherIndex(Me, rtn) Then
                    Return rtn
                Else
                    Return npos
                End If
            End Function

            Public Shared Operator +(ByVal this As node) As valueT
                If this.hasValue Then
                    Return this.value
                Else
                    Return Nothing
                End If
            End Operator

            Public Function Clone() As Object Implements System.ICloneable.Clone
                Dim rtn As node = Nothing
                rtn = alloc(Me)
                rtn.initial(child.Length())
                copy(rtn.value, value)
                copy(rtn.hasValue, hasValue)
                copy(rtn._length, length)

                Return rtn
            End Function
        End Class

        Protected Shared _end As iterator = Nothing

        Public Function begin() As iterator
            Return New iterator(root)
        End Function

        Public Function rbegin() As iterator
            Dim it As node = root
            If max(it) Then
                Return New iterator(it)
            Else
                Return _end
            End If
        End Function

        Public Function [end]() As iterator
            Return _end
        End Function

        Public Function rend() As iterator
            Return _end
        End Function

        Private Shared Function childCount() As Int64
            Return +(_cc)
        End Function

        Protected Shared Function findFatherIndex(ByVal it As node, ByRef index As UInt32) As Boolean
            If it.father Is Nothing Then
                Return False
            Else
                Dim i As UInt32
                For i = 0 To it.father.child.Length() - 1
                    If Object.ReferenceEquals(it.father.child(i), it) Then
                        index = i
                        Exit For
                    End If
                Next

                assert(i < it.father.child.Length() _
                       , "cannot get a child of father reference equals to the node.")
                Return True
            End If
        End Function

        Protected Shared Function max(ByRef it As node) As Boolean
            If it Is Nothing Then
                Return False
            Else
                Dim childCount As UInt32
                childCount = it.child.Length()
                While Not it.child(childCount - 1) Is Nothing
                    it = it.child(childCount - 1)
                End While

                Return True
            End If
        End Function

        Protected Shared Function min(ByRef it As node) As Boolean
            If it Is Nothing Then
                Return False
            Else
                While Not it.child(0) Is Nothing
                    it = it.child(0)
                End While

                Return True
            End If
        End Function

        Public Sub New()
            clear()
        End Sub

        Default Public Property data(ByVal k() As keyT) As valueT
            Get
                Return (++find(k, True, False))
            End Get
            Set(ByVal value As valueT)
                Dim w As iterator
                w = find(k, True, False)
                w.instance().hasValue = True
                copy(w.instance().value, value)
            End Set
        End Property

        Public Function findfront(ByVal k() As keyT _
                                , Optional ByVal findfrontAction As DfindFrontAction = Nothing) As iterator
            Return find(k, False, True, findfrontAction)
        End Function

        Public Function find(ByVal k() As keyT) As iterator
            Return find(k, False, False)
        End Function

        Private Function find(ByVal k() As keyT, ByVal autoInsert As Boolean, ByVal findfront As Boolean, _
                              Optional ByRef findfrontAction As DfindFrontAction = Nothing) As iterator
            Dim i As Int32
            Dim w As node
            Dim l As node = Nothing
            Dim index As Int32

            w = root
            For i = 0 To k.Length() - 1
                If w Is Nothing Then
                    Exit For
                Else
                    index = keyToIndex(k(i))
                    If w.child(index) Is Nothing Then
                        If autoInsert Then
                            w.child(index) = New node(childCount())
                            w.child(index)._length = i + 1
                            w.child(index).father = w
                        ElseIf findfront Then
                            Exit For
                        End If
                    End If
                    w = w.child(index)
                    If Not w Is Nothing AndAlso w.hasValue Then
                        l = w
                        If Not findfrontAction Is Nothing Then
                            findfrontAction(l)
                        End If
                    End If
                End If
            Next

            If findfront Then
                Return New iterator(l)
            Else
                Return New iterator(w)
            End If
        End Function

        Public Function insert(ByVal k() As keyT) As iterator
            Dim w As iterator
            w = find(k, True, False)
            w.instance().hasValue = False

            Return w
        End Function

        Public Function insert(ByVal k() As keyT, ByVal v As valueT) As iterator
            Dim w As iterator
            w = insert(k)
            With (+w)
                .hasValue = True
                copy(.value, v)
            End With

            Return w
        End Function

        Public Function [erase](ByVal k() As keyT) As Boolean
            Dim w As iterator
            w = find(k, False, False)
            If w = [end]() Then
                Return False
            Else
                w.instance().hasValue = False
                w.instance().value = Nothing

                Return True
            End If
        End Function

        Public Function remove(ByVal k() As keyT) As Boolean
            Return [erase](k)
        End Function

        Protected Friend Sub copyNode(ByRef dest As node, ByVal source As node)
            If Not source Is Nothing Then
                copy(dest, source)
                Dim i As Int32
                For i = 0 To childCount() - 1
                    If Not source.child(i) Is Nothing Then
                        copyNode(dest.child(i), source.child(i))
                        dest.child(i).father = dest
                    End If
                Next
            End If
        End Sub

        Public Function Clone() As Object Implements ICloneable.Clone
            Dim rtn As trie(Of keyT, valueT, _childCount, _keyToIndex) = alloc(Me)
            copyNode(rtn.root, root)

            Return rtn
        End Function

        Public Sub delsubtree(ByRef r As node)
            Dim i As Int32
            If Not r Is Nothing Then
                For i = 0 To childCount() - 1
                    delsubtree(r.child(i))
                    r.child(i) = Nothing
                Next
                r.value = Nothing
            End If
            r = Nothing
        End Sub

        Public Sub clear()
            delsubtree(root)
            root = New node(childCount())
        End Sub

        Shared Sub New()
            _end = New iterator(convertor.cast(Of node)(Nothing))
            _cc = alloc(Of _childCount)()
            keyToIndex = alloc(Of _keyToIndex)()
        End Sub

        Private Class amuActions
            Public Shared t As chartrie(Of Int32) = Nothing
            Public Shared m As map(Of String, Int32) = Nothing

            Private Shared Function randomString() As String
                Return strleft(createGUID(), 4)
            End Function

            Private Shared Function randomInt32() As Int32
                Return rnd(minInt32, maxInt32, True)
            End Function

            Public Shared Sub find()
                Dim s As String = Nothing
                s = randomString()
                assert((m.find(s) = m.end()) = (t.find(c_str(s)) = t.end()))
            End Sub

            Public Shared Sub insert()
                Dim s As String = Nothing
                Dim i As Int32 = 0
                s = randomString()
                i = randomInt32()
                t.insert(c_str(s), i)
                m.insert(s, i)
                assert(t.find(c_str(s)) <> t.end())
            End Sub

            Public Shared Sub [erase]()
                Dim s As String = Nothing
                s = randomString()
                assert(t.remove(c_str(s)) = m.erase(s))
            End Sub

            Public Shared Sub clear()
                t.clear()
                m.clear()
            End Sub
        End Class

        Public Shared Sub automaticalUnittest()
            amuActions.t = New chartrie(Of Int32)()
            amuActions.m = New map(Of String, Int32)()
            Dim roundcount As Int64 = 10240
            If isreleasebuild() Then
                roundcount *= 20
            End If

            raiseError("******** chartrie(of int32) automatical unittest start ********", _
                       errorHandle.errorType.application)
            randomrun.invoke(roundcount, New randomrun.info(0.35, AddressOf amuActions.find), _
                                         New randomrun.info(0.4, AddressOf amuActions.insert), _
                                         New randomrun.info(0.2, AddressOf amuActions.erase), _
                                         New randomrun.info(0.05, AddressOf amuActions.clear))
            raiseError("******** chartrie(of int32) automatical unittest finish *******", _
                       errorHandle.errorType.application)
        End Sub
    End Class

    Public Class chartrie(Of valueT)
        Inherits trie(Of Char, valueT, _maxUInt16, _char_to_uint32)
    End Class

    Public Class bytetrie(Of valueT)
        Inherits trie(Of Byte, valueT, _maxUInt8, _byte_to_uint32)
    End Class

    Public Class stringtrie(Of valueT)
        Inherits bytetrie(Of valueT)

        Public Shadows Function find(ByVal s As String) As iterator
            Return MyBase.find(string_byte(s))
        End Function

        Public Shadows Function insert(ByVal s As String, ByVal v As valueT) As iterator
            Return MyBase.insert(string_byte(s), v)
        End Function

        Public Shadows Function insert(ByVal s As String) As iterator
            Return MyBase.insert(string_byte(s))
        End Function

        Public Shadows Function [erase](ByVal s As String) As Boolean
            Return MyBase.erase(string_byte(s))
        End Function

        Public Shadows Function remove(ByVal s As String) As Boolean
            Return MyBase.remove(string_byte(s))
        End Function

        Default Public Shadows Property data(ByVal s As String) As valueT
            Get
                Return MyBase.data(string_byte(s))
            End Get
            Set(ByVal value As valueT)
                MyBase.data(string_byte(s)) = value
            End Set
        End Property

        Public Shared Function first(ByVal it As iterator) As String
            If it Is Nothing OrElse (+it) Is Nothing Then
                Return Nothing
            Else
                Return byte_string((+it).first())
            End If
        End Function
    End Class
End Namespace
